package com.ly.algorithm.offerpointer;
import	java.util.Stack;

/**
 * @Classname Offer33
 * @Description
 *
 * 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
 *
 * 参考以下这颗二叉搜索树：
 *
 *      5
 *     / \
 *    2   6
 *   / \
 *  1   3
 *
 *
 * @Date 2021/1/29 15:10
 * @Author 冷心影翼
 */
public class Offer33 {

    public static void main(String[] args) {
        Solution33 solution33 = new Solution33();
        System.out.println(solution33.verifyPostorder(new int[]{1, 3, 2, 6, 5}));
        System.out.println(solution33.verifyPostorderByStack(new int[]{1, 3, 2, 6, 5}));
    }
}


class Solution33 {

    public boolean verifyPostorder(int[] postorder) {
        return recursion(postorder,0,postorder.length-1);
    }

    public boolean recursion(int[] postorder,int left,int right) {
        if(left >= right) {
            return true;
        }
        int p = left;
        while (postorder[p] < postorder[right]) {
            p++;
        }
        int m = p;
        while (postorder[p] > postorder[right]) {
            p++;
        }
        return p == right && recursion(postorder,left,m-1) && recursion(postorder,m,right-1);
    }

    public boolean verifyPostorderByStack(int[] postorder) {
        Stack<Integer> stack = new Stack<> ();
        int root = Integer.MAX_VALUE;
        for (int i = postorder.length-1; i >= 0 ; i--) {
            if(postorder[i]>root) {
                return false;
            }
            while (!stack.isEmpty() && stack.peek() > postorder[i]) {
                root = stack.pop();
            }
            stack.push(postorder[i]);
        }
        return true;
    }
}